백준 7579번
오늘 풀어본 문제는 백준의 7579번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 ‘활성화’되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.
하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.
메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화 하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다
현재 $N$ 개의 앱, $A_1, …, A_N$ 이 활성화 되어 있다고 가정하자. 이들 앱 $A_i$ 는 각각 $m_i$ 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 $A_i$ 를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 $c_i$ 라고 하자. 이러한 상황에서 사용자가 새로운 앱 $B$ 를 실행하고자 하여, 추가로 $M$ 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 $A_1, …, A_N$ 중에서 몇 개를 비활성화 하여 $M$ 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 $c_i$ 의 합을 최소화하여 필요한 메모리 $M$ 바이트를 확보하는 방법을 찾아야 한다.
입력
입력은 $3$ 줄로 이루어져 있다. 첫 줄에는 정수 $N$ 과 $M$ 이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 $N$ 개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 $N$ 개의 정수는 현재 활성화 되어 있는 앱 $A_1, …, A_N$ 이 사용 중인 메모리의 바이트 수인 $m_1, …, m_N$ 을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 $c_1, …, c_N$ 을 의미한다
단, $1 \le N \le 100$, $1 \le M \le 10,000,000$ 이며, $1 \le m_1, …, m_N \le 10,000,000$ 을 만족한다. 또한, $0 \le c_1, …, c_N \le 100$ 이고, $M \le m_1 + m_2 + … + m_N$ 이다.
출력
필요한 메모리 $M$ 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.
풀이과정
1번째 시도
문제를 보고 배낭 문제라는 것을 알 수 있었다. 예전에 사용했던 배낭 문제 코드를 그대로 가져와 확보되는 용량을 가치로, 필요한 비용을 무게로 둔 뒤 입출력 조건을 맞추어 수정하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<int>> knapsack(101, vector<int>(10001, 0));
vector<int> memory(101, 0);
vector<int> cost(101, 0);
for (int i=1; i<=N; i++) {
cin >> memory[i];
}
for (int i=1; i<=N; i++) {
cin >> cost[i];
}
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
if (cost[i] > j) {
knapsack[i][j] = knapsack[i - 1][j];
}
else {
knapsack[i][j] = max(knapsack[i - 1][j], knapsack[i - 1][j - cost[i]] + memory[i]);
}
}
}
for (int i=1; i<=M; i++) {
if (knapsack[N][i] >= M) {
cout << i;
break;
}
}
return 0;
}
실행 결과 ‘런타임 에러 (OutOfBounds)’ 가 떴다.
2번째 시도
런타임 에러가 뜬 원인으로 바로 알 수 있었던 것은 $M$ 의 범위였다. 이를 해결하기 위해서 knapsack 변수를 일차원 배열로 바꾸고, 인덱스를 비용으로, 저장된 값을 최대 메모리로 하여 점화식을 재구성하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> knapsack(10001, 0);
vector<int> memory(101, 0);
vector<int> cost(101, 0);
for (int i=1; i<=N; i++) {
cin >> memory[i];
}
for (int i=1; i<=N; i++) {
cin >> cost[i];
}
for (int i=1; i<=N; i++) {
for(int j=10000; j >= cost[i]; j--){
knapsack[j] = max(knapsack[j], knapsack[j - cost[i]] + memory[i]);
}
}
for (int i=1; i<=10000; i++) {
if (knapsack[i] >= M) {
cout << i;
break;
}
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
3번째 시도
질문 게시판을 돌아다닌 결과, 내가 현재 짠 코드에는 필요한 비용이 $0$ 인 경우를 고려하지 않고 있었다. 출력 과정에서 검사 범위를 수정하는 방식으로 해결을 시도하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> knapsack(10001, 0);
vector<int> memory(101, 0);
vector<int> cost(101, 0);
for (int i=1; i<=N; i++) {
cin >> memory[i];
}
for (int i=1; i<=N; i++) {
cin >> cost[i];
}
for (int i=1; i<=N; i++) {
for(int j=10000; j >= cost[i]; j--){
knapsack[j] = max(knapsack[j], knapsack[j - cost[i]] + memory[i]);
}
}
for (int i=0; i<=10000; i++) {
if (knapsack[i] >= M) {
cout << i;
break;
}
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
배낭 문제는 몇 번을 해도 잘 익숙해지지 않는 것 같다… 역시 CLASS 별 문제는 몇 개만 풀고 말게 아니라 싹 다 풀어보는게 적응과 이해, 그리고 실력 증진에 도움이 되는 것 같다.
이 문제를 풀게되어, 이제 CLASS 5 의 에센셜 문제는 단 한개만이 남게 되었다. 내일 한 문제를 더 푸는 더 성공하면 은색 휘장을 달 수 있게 되는 것이다! 은색 휘장을 달면 프로필이 얼마나 더 예뻐질까? 기대가 된다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/7579